package datatypes.kdTree;

import java.util.Iterator;
import java.util.Stack;

import datatypes.Vertex;

class RangeIterator implements Iterator<Vertex>, Iterable<Vertex> {
	private Range queryRange;
	private Stack<KdTreeElement> reportAll;
	private Stack<KdTreeElement> currentElement;
	
	RangeIterator(Range range, KdTree tree) {
		this.queryRange = range;
		currentElement = new Stack<KdTreeElement>();
		currentElement.push(tree.root);
		reportAll = new Stack<KdTreeElement>();
	}
	
	/**
	 * See algorithm on page 103. Line numbers given as comments.
	 * @param element
	 * @param queryRange
	 * @param foundLeaves
	 * @return
	 */
	private boolean search() {
		KdTreeElement element = currentElement.pop();
		if (element.isLeaf()) {
			if (queryRange.contains(element.median)) {
				reportAll.push(element);
				return true;
			}
			return false;
		}
		
		boolean foundStuff = false;
		
		KdTreeElement branch;
		branch = element.left;
		
		if (branch != null) {
			if (queryRange.contains(branch.range)) {
				reportAll.push(branch);
				foundStuff = true;
			} else {
				if (queryRange.intersects(branch.range)) {
					currentElement.push(branch);
				}
			}
		}
		
		branch = element.right;
		
		if (branch != null) {
			if (queryRange.contains(branch.range)) {
				reportAll.push(branch);
				foundStuff = true;
			} else {
				if (queryRange.intersects(branch.range)) {
					currentElement.push(branch);
				}
			}
		}
		return foundStuff;
	}
	
	/**
	 * Returns a list of KdTreeElements of the given subtree.
	 * See {@link #bfsTree()} or {@link #dfsTree()} to get a list of the whole tree.
	 * @param rootElement
	 * @param reportNodes If false, all nodes will be omitted.
	 * @param reportLeaves If false, all leaves will be omitted.
	 * @return
	 */
	public Vertex dfsTree() {
		
		KdTreeElement currentNode;
		
		while(!reportAll.isEmpty()) {
			currentNode = reportAll.pop();
			if ( currentNode.isLeaf() ) {
				return currentNode.median;
			}
			reportAll.add(currentNode.right);
			reportAll.add(currentNode.left);
		}
		return null;
	}
	
	@Override
	public boolean hasNext() {
		if (!reportAll.empty()) {
			return true;
		}
		while (!currentElement.empty()) {
			if (search()) {
				return true;
			}
		}
		return false;
	}

	@Override
	public Vertex next() {
		return dfsTree();
	}

	@Override
	public void remove() {
		throw new UnsupportedOperationException();
	}

	@Override
	public Iterator<Vertex> iterator() {
		return this;
	}

}
